◀ Prev · Parts · Full · Next ▶

In other cases, even if the initial results are of purely theoretical interest, over time, with an improved understanding, the algorithms may be refined to become more practical. One such example is the initial PTAS for Euclidean TSP by Sanjeev Arora (and independently by Joseph Mitchell) which had a prohibitive running time of n O ( 1 / ϵ ϵ ) {\displaystyle n^{O(1/\epsilon )}} for a 1 + ϵ ϵ {\displaystyle 1+\epsilon } approximation.cite-ref-10[10] Yet, within a year these ideas were incorporated into a near-linear time O ( n log ⁡ ⁡ n ) {\displaystyle O(n\log n)} algorithm for any constant ϵ ϵ > 0 {\displaystyle \epsilon >0} .cite-ref-11[11]

Given an optimization problem:

Π Π : I × × S {\displaystyle \Pi :I\times S}

where Π Π {\displaystyle \Pi } is an approximation problem, I {\displaystyle I} the set of inputs and S {\displaystyle S} the set of solutions, we can define the cost function:

c : S → → R + {\displaystyle c:S\rightarrow \mathbb {R} ^{+}}

and the set of feasible solutions:

∀ ∀ i ∈ ∈ I , S ( i ) = s ∈ ∈ S : i Π Π s {\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}

finding the best solution s ∗ ∗ {\displaystyle s^{*}} for a maximization or a minimization problem:

s ∗ ∗ ∈ ∈ S ( i ) {\displaystyle s^{*}\in S(i)} , c ( s ∗ ∗ ) = m i n / m a x c ( S ( i ) ) {\displaystyle c(s^{*})=min/max\ c(S(i))}

◀ Prev · Parts · Full · Next ▶